#include "graph.h"
/*necessario per usare INT_MAX*/
#include <limits.h>
/*per usare FLT_MAX*/
#include <float.h>
/*necessario per checkMalloc()*/
#include "main-tools.h"
#include <stdio.h>
#include <stdlib.h>

Pgraph initGraph(int* N,float T,float Q, int depot){
	Pgraph result=(Pgraph)malloc(sizeof(Graph));
	checkMalloc(result,"graph.c:initGraph#1");
	result->N=N;
	result->T=T;
	result->Q=Q;
	result->depot=depot;
	result->E=0;
	result->am = (AdjMat)malloc(*N*sizeof(PedgeGraph));
	checkMalloc(result->am,"graph.c:initGraph#2");
	result->timeWM = (WeightMat)malloc(*N*sizeof(Pweight));
	checkMalloc(result->timeWM,"graph.c:initGraph#3");
	result->loadWM = (WeightMat)malloc(*N*sizeof(Pweight));
	checkMalloc(result->loadWM,"graph.c:initGraph#4");
	int i;
	for (i=0; i<*N; i++){
		result->am[i] = (PedgeGraph)malloc(*N*sizeof(EdgeGraph));
		checkMalloc(result->am[i],"graph.c:initGraph#5");
		result->timeWM[i] = (Pweight)malloc(*N*sizeof(Weight));
		checkMalloc(result->timeWM[i],"graph.c:initGraph#6");
		result->loadWM[i] = (Pweight)malloc(*N*sizeof(Weight));
		checkMalloc(result->loadWM[i],"graph.c:initGraph#7");
	}
	return result;
}

Pgraph initCompleteGraph(int* N, float T, float Q,int depot, EdgeGraph edge){
	Pgraph result = (Pgraph)malloc(sizeof(Graph));
	checkMalloc(result,"graph.c:initGraph#1");
	result->N=N;
	result->T=T;
	result->Q=Q;
	result->E=0;
	result->am = (AdjMat)malloc(*N*sizeof(PedgeGraph));
	checkMalloc(result->am,"graph.c:initGraph#2");
	result->timeWM = (WeightMat)malloc(*N*sizeof(Pweight));
	checkMalloc(result->timeWM,"graph.c:initGraph#3");
	result->loadWM = (WeightMat)malloc(*N*sizeof(Pweight));
	checkMalloc(result->loadWM,"graph.c:initGraph#4");
	int i,j;
	for (i=0; i<*N; i++){
		result->am[i] = (PedgeGraph)malloc(*N*sizeof(EdgeGraph));
		checkMalloc(result->am,"graph.c:initGraph#3");
		for (j=0; j<*N; j++){
			result->am[i][j].t = edge.t;
			result->am[i][j].d = edge.d;
			result->am[i][j].p = edge.p;
		}
		result->timeWM[i] = (Pweight)malloc(*N*sizeof(Weight));
		checkMalloc(result->timeWM[i],"graph.c:initGraph#6");
		result->loadWM[i] = (Pweight)malloc(*N*sizeof(Weight));
		checkMalloc(result->loadWM[i],"graph.c:initGraph#7");
	}
	return result;
}

/* Casistica delle preferenze - pat 17 giugno
 * si ipotizza che i tempi t NON possano essere nulli.
 * ~ significa normale, cioè non trattata particolarmente
 *
 * 	p	d	tipico	timeWM	loadWM	totWM (smart, wise)
 * --------------------------------------
 * 	0	0	 sì		  0		  0		  0				sicuramente worsen perchè aumenta tau
 * 	!0	0	 no		  ~		  Inf	  Inf		FUTURE IMPL
 * 	0	!0	 no		  0		  0		  0			FUTURE IMPL
 *  !0	!0	 sì		  ~		  ~		  ~				maggiore il peso, migliore l'edge profittabile
 */
void initSmartWeights(Pgraph pg){
	EdgeID id;
	for (id.i=0; id.i<(*pg->N); id.i++){
		for (id.j=id.i+1; id.j<*pg->N; id.j++){

			pg->timeWM[id.i][id.j] = /*pg->am[id.i][id.j].t== 0 ?
					- INFINITE_WEIGHT : */
					pg->am[id.i][id.j].p / pg->am[id.i][id.j].t;

			/* vecchia regola.
			pg->loadWM[id.i][id.j] = pg->am[id.i][id.j].d == 0 ?
					- INFINITE_WEIGHT :
					pg->am[id.i][id.j].p / pg->am[id.i][id.j].d; */
			if( !pg->am[id.i][id.j].d && pg->am[id.i][id.j].p ) //FIXME gestire meglio
				printf("\n\nPESO NON VALIDO: il grafo non è un input plausibile. Contattare gli sviluppatori. Esecuzione instabile.\n\n");

			if( !pg->am[id.i][id.j].d && !pg->am[id.i][id.j].p )
				pg->loadWM[id.i][id.j] = 0; //arco non profittabile, quindi (per i soli carichi) conveniente al minimo possibile (0)
			else
				pg->loadWM[id.i][id.j] = pg->am[id.i][id.j].p / pg->am[id.i][id.j].d;
		}
	}
}

PedgeGraph getEdgeGraph(Pgraph pg, PedgeID edge){
	return (edge->i > edge->j?
				&(pg->am[edge->j][edge->i]):
				&(pg->am[edge->i][edge->j]));
}

Weight getEdgeLoadWeight(Pgraph pg,PedgeID edge){
	return (edge->i > edge->j?
					pg->loadWM[edge->j][edge->i]:
					pg->loadWM[edge->i][edge->j]);
}

Weight getEdgeTimeWeight(Pgraph pg,PedgeID edge){
	return (edge->i > edge->j?
					pg->timeWM[edge->j][edge->i]:
					pg->timeWM[edge->i][edge->j]);
}

void setEdgeGraph(Pgraph pg,PedgeID id, int t,int d,int p){
	//verifica che l'edge passato sia validato correttamente. Se non lo è, NON effettua la validazione
	if (id->i > id->j){
		pg->am[id->j][id->i].t=t;
		pg->am[id->j][id->i].d=d;
		pg->am[id->j][id->i].p=p;
		return;
	}
	pg->am[id->i][id->j].t=t;
	pg->am[id->i][id->j].d=d;
	pg->am[id->i][id->j].p=p;
	if (id->i == id->j)
		return;
}

void setEdgeGraphTime(Pgraph pg,PedgeID id,int t){
	pg->am[id->i][id->j].t=t;
}

void setEdgeGraphByIndexes(Pgraph pg,int i,int j, int t,int d,int p){
	EdgeID id={i,j};
	//printEdgeID(stdout,&id);
	//printf(" vecchio t: %d nuovo t: %d ",getEdge(pg,&id).t,t);
	setEdgeGraph(pg,&id,t,d,p);
	//printf("impostarto ora ad: %d\n",getEdge(pg,&id).t);
}

int getEdgeGraphValue(Pgraph pg, int i, int j, char type){
	if(type=='t')
		return pg->am[i][j].t;
	else if(type=='d')
		return pg->am[i][j].d;
	else
		return pg->am[i][j].p;
}

bool isEdgeProfitable(Pgraph pg, PedgeID pid) {
	return getEdgeGraph(pg, pid)->p && getEdgeGraph(pg, pid)->d;
}

Weight evaluateEdge (Pgraph pg, PedgeID pid, int tau, int theta, short mode){
	switch (mode){
	case EVAL_PURE: {
		return (Weight)getEdgeGraph(pg, pid)->p;
	}
	case EVAL_SMART: {
		return (getEdgeTimeWeight(pg, pid) + getEdgeLoadWeight(pg, pid));
	}
	case EVAL_WISE: {
		return getEdgeTimeWeight(pg, pid)*(pg->T-tau) + getEdgeLoadWeight(pg, pid)*(pg->Q-theta);
	}
	}
	return EVAL_FAILED;
}

Weight evaluateNonProfitableEdge(Pgraph pg, PedgeID pid, int tau, short mode){
	switch (mode){
	case EVAL_PURE: {
		return (Weight)getEdgeGraph(pg, pid)->t;
	}
	case EVAL_SMART: {
		return getEdgeTimeWeight(pg, pid);
	}
	case EVAL_WISE: {
		return getEdgeTimeWeight(pg, pid)*(pg->T-tau);
	}
	}
	return EVAL_FAILED;
}

void printGraph(FILE* f, Pgraph pg){
	fprintf(f, "numero di nodi: %d\n", *pg->N);
	fprintf(f, "numero di archi: %d\n", pg->E);
	fprintf(f, "capacita' massima: %d\n", pg->T);
	fprintf(f, "tempo massimo: %d\n", pg->Q);
	fprintf(f, "nodo deposito: %d\n", pg->depot);
	printAdjMatrix(f,pg,'t');
	printAdjMatrix(f,pg,'d');
	printAdjMatrix(f,pg,'p');
}

void printWholeMatrix(FILE* f, Pgraph pg) {
	int i,j, temp;

	fprintf(f, "Matrix of Times,Demands and Profits\n\ni\\f|");
	for(i=0; i<*(pg->N); i++) //prints row header
		fprintf(f, "%3d|",i+1);
	fprintf(f, "\n\n");

	for(i=0; i<*pg->N; i++){ //prints rows
		//prima sottoriga: times
		fprintf(f, "   |");
		for(j=0; j<i+1; j++)
					fprintf(f, "---|");
		for(j=i+1; j<*pg->N; j++)
			if((temp = getEdgeGraphValue(pg,i,j,'t'))<INFINITE)
				fprintf(f, "%3d|", temp);
			else
				fprintf(f, "---|");
		fprintf(f, "\n");
		//seconda sottoriga: demands
		fprintf(f, "%3d|",i+1);
		for(j=0; j<i+1; j++)
					fprintf(f, "---|");
		for(j=i+1; j<*pg->N; j++)
			fprintf(f, "%3d|", getEdgeGraphValue(pg,i,j,'d'));
		fprintf(f, "\n");
		//terza sottoriga: profits
		fprintf(f, "   |");
		for(j=0; j<i+1; j++)
					fprintf(f, "---|");
		for(j=i+1; j<*pg->N; j++)
			fprintf(f, "%3d|", getEdgeGraphValue(pg,i,j,'p'));
		fprintf(f, "\n\n");
	}
}

void printAdjMatrix(FILE* f, Pgraph pg, char type) {
	int i,j, temp;

	if(type=='t')
		fprintf(f, "Matrix of Times\ni\\f|");
	else if(type=='d')
		fprintf(f, "Matrix of Demands\ni\\f|");
	else if(type=='p')
		fprintf(f, "Matrix of Profits\ni\\f|");

	for(i=0; i<*pg->N; i++) //prints row header
		fprintf(f, "%3d|",i+1);
	fprintf(f, "\n");

	for (i=0; i<*pg->N; i++){
		fprintf(f, "%3d|", i+1);
		for (j=0; j<=i; j++)
			fprintf(f, "---|");
		for (j=i+1; j<*pg->N; j++){
			temp = getEdgeGraphValue(pg, i, j, type);
			if (temp<INFINITE)
				fprintf(f, "%3d|",temp);
			else
				fprintf(f,"inf|");
		}
		fprintf(f,"\n");
	}
}

void printEdgeFromGraph(FILE* f, Pgraph pg, PedgeID pe) {
	fprintf(f,"e=");
	printEdgeID(f,pe);
	fprintf(f, " | ");
	printEdgeGraph(f, getEdgeGraph(pg, pe));
}

int minDistance(int dist[], bool sptSet[], int N) {
   int min = INFINITE;
   int i, min_index;
   for (i=0; i<N; i++)
     if (sptSet[i] == false && dist[i] < min)
         min = dist[i], min_index = i;

   return min_index;
}

void dijkstra(Pgraph pg, int src) {
	 int N = *(pg->N);
	 int i;
	 int j;
	 int v;
	 EdgeID edge1;
	 EdgeID edge2;
	 //contiene la minima distanza che intercorre tra src e l'i-esimo nodo
     int dist[N];
     // sptSet[i] will true if vertex i is included in shortest path tree or shortest distance from src to i is finalized
     bool sptSet[N];

     // Initialize all distances as INFINITE and stpSet[] as false
     for (i=0; i<N; i++){
        dist[i] = INFINITE;
        sptSet[i] = false;
     }
     // Distance of source vertex from itself is always 0
     dist[src] = 0;

     // Find shortest path for all vertices
     for (v=0; v<N-1; v++) {
        /* Pick the minimum distance vertex from the set of vertices not
    	 * yet processed. u is always equal to src in first iteration.
    	 */
        int u = minDistance(dist, sptSet, N);
        // Mark the picked vertex as processed
        sptSet[u] = true;
        // Update dist value of the adjacent vertices of the picked vertex.
        for (j=0; j<N; j++){
        	// Update dist[j] only if is not in sptSet, there is an edge from
        	// u to j, and total weight of path from src to j through u is
        	// smaller than current value of dist[j]
        	edge1.i=u;
        	edge1.j=j;
        	edge2.i=j;
        	edge2.j=src;

        	if (!sptSet[j] && getEdgeGraph(pg,&edge1)->t && (dist[u] + getEdgeGraph(pg,&edge1)->t)<dist[j]){
        		dist[j]= dist[u]+getEdgeGraph(pg,&edge1)->t;
        		setEdgeGraphByIndexes(pg,j,src,dist[j],getEdgeGraph(pg,&edge2)->d,getEdgeGraph(pg,&edge2)->p);
        	}
        }
     }
}

void dijkstraFiller(Pgraph pg) {
	int i;
	for(i=0; i<*(pg->N); i++)
		dijkstra(pg,i);
}

void graphCorrector(Pgraph pg){
	EdgeID ab;
	EdgeID ac;
	EdgeID bc;

	int lato_ab;
	int lato_ac;
	int lato_bc;

	//si cicla sulle righe
	for (ab.i=0; ab.i<(*(pg->N)-2); ab.i++){
		for (ab.j = (ab.i+1); ab.j < (*(pg->N)-1); ab.j++){//fino a N-1 perche' sto cercando ancora il primo vertice
			if (pg->am[ab.i][ab.j].t>=INFINITE)//l'arco non esiste. Passo oltre
				continue;
			//trovato primo arco ab!
			lato_ab=pg->am[ab.i][ab.j].t;
			ac.i=ab.i;
			for (ac.j = (ab.j+1); ac.j < *(pg->N); ac.j++){
				if (pg->am[ac.i][ac.j].t>=INFINITE)//il secondo lato non esiste. Passo oltre
					continue;
				//trovato secondo arco "b"
				lato_ac=pg->am[ac.i][ac.j].t;
				//calcolo il terzo arco del presunto triangolo
				bc.i=ab.j; bc.j=ac.j;
				//ora verifico se c'è un triangolo
				if (pg->am[bc.i][bc.j].t>=INFINITE)
					continue;
				//c'è un triangolo perché c'e' "c", quindi verifico se la disuguaglianza e' verificata
				lato_bc=pg->am[ab.j][ac.j].t;
				//verifico l'assenza della disuaglianza triangolare:
				if ((lato_ab+lato_ac)<lato_bc){//il lato bc dovrebbe essere piu' piccolo di ab+ac!
					//printEdgeID(stdout,&ab); fprintf(stdout,"\t"); printEdgeID(stdout,&ac); fprintf(stdout,"\t<\t"); printEdgeID(stdout,&bc); fprintf(stdout,"\n");
					//printf("%d\t%d\t<\t%d\n",lato_ab,lato_ac,lato_bc);
					setEdgeGraphTime(pg,&bc,lato_ab+lato_ac);
					continue;
				}
				if ((lato_ab+lato_bc)<lato_ac){//il lato ac dovrebbe essere piu' piccolo di ab+bc!
					//printEdgeID(stdout,&ab); fprintf(stdout,"\t"); printEdgeID(stdout,&bc); fprintf(stdout,"\t<\t"); printEdgeID(stdout,&ac); fprintf(stdout,"\n");
					//printf("%d\t%d\t<\t%d\n",lato_ab,lato_bc,lato_ac);
					setEdgeGraphTime(pg,&ac,lato_ab+lato_bc);
					continue;
				}
				if ((lato_ac+lato_bc)<lato_ab){//il lato ab dovrebbe essere piu' piccolo ac+bc
					//printEdgeID(stdout,&ac); fprintf(stdout,"\t"); printEdgeID(stdout,&bc); fprintf(stdout,"\t<\t"); printEdgeID(stdout,&ab); fprintf(stdout,"\n");
					//printf("%d\t%d\t<\t%d\n",lato_ac,lato_bc,lato_ab);
					setEdgeGraphTime(pg,&ab,lato_ac+lato_bc);
					continue;
				}
			}
		}
	}
	/*perché N-2? disegniamo la matrice di adiacenza, per esempio una 5x5 dove x sono valori ripetuti o comunque non accettabili:
	 * -----------
	 * |x|a| |a| |
	 * -----------
	 * |x|x| |a| |
	 * -----------
	 * |x|x|x| | |
	 * -----------
	 * |x|x|x|x| |
	 * -----------
	 * |x|x|x|x|x|
	 * -----------
	 * un triangolo appare come in figura.
	 * bisognera' ciclare sulle righe non da N (5), me neanche da N-1 (4) perché lì è impossibile trovare triangoli non ancora intercettati.
	 * Si parte da N-2
	 *
	 *
	 */
}

void printRemainingResources(FILE* f, Pgraph pg, int tau, int theta) {
	fprintf(f, "Tempo rimanente: %d, Risorse rimanenti: %d\n", pg->T-tau, pg->Q-theta);
}
